import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created by losor on 2017/3/18.
 */
public class _219_ContainsDuplicateII {


    public boolean containsNearbyDuplicate(int[] nums, int k) {
            if (nums.length <2){
                return false;
            }
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                if (i - map.get(nums[i])<=k){
                    return true;
                }
            }
            else{
                map.put(nums[i],i);
            }
        }
        return false;
    }

    //因为要找的是是否有两个相同的num下标的追偿距离是k，所以就是将i到i-k个数字放到set里，先删掉i-k-1的元素，然后看第i个元素，如果有的话就说明出现了这样的数
    public boolean containsNearbyDuplicateBigBoss(int[] nums, int k){
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (i>k) set.remove(nums[i-k-1]);
            if (!set.add(nums[i])) return true;
        }
        return false;
    }
}
